{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Palindrome Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大回文数乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数 n ，返回 <em>可表示为两个 <code>n</code>&nbsp;位整数乘积的 <strong>最大回文整数</strong></em> 。因为答案可能非常大，所以返回它对 <code>1337</code> <strong>取余</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2\n",
    "<b>输出：</b>987\n",
    "<strong>解释：</strong>99 x 91 = 9009, 9009 % 1337 = 987\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> n = 1\n",
    "<strong>输出：</strong> 9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-palindrome-product](https://leetcode.cn/problems/largest-palindrome-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-palindrome-product](https://leetcode.cn/problems/largest-palindrome-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        # 如果 n=1，答案是 9\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        \n",
    "        # 计算 n 位数的最大值和最小值\n",
    "        upper = 10 ** n - 1\n",
    "        lower = 10 ** (n - 1)\n",
    "        \n",
    "        # 从最大值开始，构造可能的回文数\n",
    "        for a in range(upper, lower - 1, -1):\n",
    "            candidate = int(str(a) + str(a)[::-1])  # 构造可能的回文数\n",
    "            for b in range(upper, int(candidate ** 0.5) - 1, -1):\n",
    "                if candidate / b > upper:\n",
    "                    break\n",
    "                if candidate % b == 0:\n",
    "                    return candidate % 1337\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):\n",
    "            # get p \n",
    "            p, x = left, left\n",
    "            while x:\n",
    "                p = p * 10 + x % 10\n",
    "                x //= 10\n",
    "            \n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:\n",
    "                    return p % 1337\n",
    "                x -= 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestPalindrome(self, n: int) -> int:\r\n",
    "        if n == 1:\r\n",
    "            return 9\r\n",
    "        upper = 10 ** n - 1\r\n",
    "        for left in range(upper, upper // 10, -1):  # 枚举回文数的左半部分\r\n",
    "            p, x = left, left\r\n",
    "            while x:\r\n",
    "                p = p * 10 + x % 10  # 翻转左半部分到其自身末尾，构造回文数 p\r\n",
    "                x //= 10\r\n",
    "            x = upper\r\n",
    "            while x * x >= p:\r\n",
    "                if p % x == 0:  # x 是 p 的因子\r\n",
    "                    return p % 1337\r\n",
    "                x -= 1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):  # 枚举回文数的左半部分\n",
    "            p, x = left, left\n",
    "            while x:\n",
    "                p = p * 10 + x % 10  # 翻转左半部分到其自身末尾，构造回文数 p\n",
    "                x //= 10\n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:  # x 是 p 的因子\n",
    "                    return p % 1337\n",
    "                x -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1: \n",
    "            return 9\n",
    "        \n",
    "        const = 1\n",
    "        while const < 10**n:\n",
    "            upper = 10**n - const\n",
    "            lower = int(str(upper)[::-1])\n",
    "            if const**2-lower*4 >= 0 and (const**2-lower*4)**0.5 == int((const**2-lower*4)**0.5):\n",
    "                return (upper*10**n + lower) % 1337\n",
    "            const += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "\n",
    "        tmpval = int('9'*n)\n",
    "        #s = tmpval*tmpval\n",
    "\n",
    "        def getnumber(left,lenthodd):\n",
    "            ans = left\n",
    "            if lenthodd:\n",
    "                left //= 10\n",
    "            while left>0:\n",
    "                ans = ans*10+(left%10)\n",
    "                left //= 10\n",
    "            return ans\n",
    "        l = 10**(n-1)\n",
    "        r = 10**n\n",
    "\n",
    "        def check(number):\n",
    "            x = max(10**(n-1),number//r)\n",
    "            while x*x<=number:\n",
    "                if number%x==0 and l<=number//x<r:\n",
    "                    return True\n",
    "                x += 1\n",
    "            return False\n",
    "        ans = 0 \n",
    "        for left in range(tmpval,l,-1):\n",
    "            number = getnumber(left,False)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                return ans%1337\n",
    "\n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,True)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        return ans%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        for i in range(10 ** n - 1, -1, -1):\n",
    "            num = int(str(i) + str(i)[::-1])\n",
    "            for j in range(10 ** n - 1, isqrt(num), -1):\n",
    "                if num % j == 0:\n",
    "                    return num % 1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int: \n",
    "        if n == 1:\n",
    "            return 9\n",
    "        mod = 1337\n",
    "        max_num = 10 ** n - 1\n",
    "        min_num = 10 ** (n - 1)\n",
    "        for i in range(max_num, min_num, -1):\n",
    "            s = str(i)\n",
    "            num = int(s + s[::-1])\n",
    "            for j in range(max_num, min_num, -1):\n",
    "                if num // j > max_num:\n",
    "                    break\n",
    "                if num % j == 0:\n",
    "                    return num % mod\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        res = [0, 9, 987, 123, 597, 677, 1218, 877, 475]\n",
    "        return res[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):  # 枚举回文数的左半部分\n",
    "            p, x = left, left\n",
    "            while x:\n",
    "                p = p * 10 + x % 10  # 翻转左半部分到其自身末尾，构造回文数 p\n",
    "                x //= 10\n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:  # x 是 p 的因子\n",
    "                    return p % 1337\n",
    "                x -= 1\n",
    "\n",
    "   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):\n",
    "            p, x = left, left\n",
    "            while x: \n",
    "                p = p * 10 + x % 10\n",
    "                x = x // 10\n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:\n",
    "                    return p % 1337\n",
    "                x -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        return [9,987,123,597,677,1218,877,475][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "\n",
    "        tmpval = int('9'*n)\n",
    "        #s = tmpval*tmpval\n",
    "\n",
    "        def getnumber(left,lenthodd):\n",
    "            ans = left\n",
    "            if lenthodd:\n",
    "                left //= 10\n",
    "            while left>0:\n",
    "                ans = ans*10+(left%10)\n",
    "                left //= 10\n",
    "            return ans\n",
    "        l = 10**(n-1)\n",
    "        r = 10**n\n",
    "\n",
    "        def check(number):\n",
    "            x = max(10**(n-1),number//r)\n",
    "            while x*x<=number:\n",
    "                if number%x==0 and l<=number//x<r:\n",
    "                    return True\n",
    "                x += 1\n",
    "            return False\n",
    "        lenthodd = False\n",
    "        ans = 0 \n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,False)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        if ans>0:\n",
    "            return ans%1337\n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,True)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        return ans%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1: return 9\n",
    "        upper = 10**n - 1\n",
    "        lower = 10**(n - 1)\n",
    "        for i in range(upper, lower - 1, -1):\n",
    "            candidate = int(str(i) + str(i)[::-1])\n",
    "            j = upper\n",
    "            while j * j >= candidate:\n",
    "                if candidate % j == 0:\n",
    "                    return candidate % 1337\n",
    "                j -= 1\n",
    "        return -1\n",
    "\n",
    "'''\n",
    "没看懂\n",
    "In LeetCode 479, \"Largest Palindrome Product,\" the problem asks you to find the largest palindrome made from the product of two nn-digit numbers. Since nn will be between 1 and 8, we'll write a Python function to handle these cases.\n",
    "\n",
    "If n = 1n=1, the answer is 9, so we handle that as a special case.\n",
    "Otherwise, we loop from the largest nn-digit number down to the smallest.\n",
    "For each number ii in that range, we create a candidate palindrome by appending the reversed digits of ii to ii itself.\n",
    "Then, we try to find two factors for the candidate palindrome, both of which are nn-digit numbers. We check if there's any such factor by iterating from the upper bound downward. If we find one, we return the candidate palindrome modulo 1337.\n",
    "If no palindrome is found, we return -1, although this should never happen for the given problem constraints.\n",
    "The time complexity is not easy to determine precisely due to the nested loops, but the solution works efficiently for the given constraints, and the complexity is reasonable for n \\leq 8n≤8.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1: \n",
    "            return 9\n",
    "        if n == 2:\n",
    "            return 987\n",
    "        \n",
    "        max_num = pow(10,n) - 1\n",
    "        for num in range(max_num,-1,-1):\n",
    "            palinddrome = num\n",
    "            var = num\n",
    "            while var:\n",
    "                palinddrome = palinddrome * 10 + (var % 10)\n",
    "                var //= 10\n",
    "            number = max_num\n",
    "            while number * number >= palinddrome:\n",
    "                if palinddrome % number == 0:\n",
    "                    return palinddrome % 1337\n",
    "                number -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "\n",
    "        tmpval = int('9'*n)\n",
    "        #s = tmpval*tmpval\n",
    "\n",
    "        def getnumber(left,lenthodd):\n",
    "            ans = left\n",
    "            if lenthodd:\n",
    "                left //= 10\n",
    "            while left>0:\n",
    "                ans = ans*10+(left%10)\n",
    "                left //= 10\n",
    "            return ans\n",
    "        l = 10**(n-1)\n",
    "        r = 10**n\n",
    "\n",
    "        def check(number):\n",
    "            x = max(10**(n-1),number//r)\n",
    "            while x*x<=number:\n",
    "                if number%x==0 and l<=number//x<r:\n",
    "                    return True\n",
    "                x += 1\n",
    "            return False\n",
    "        lenthodd = False\n",
    "        ans = 0 \n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,False)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,True)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        return ans%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1337\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        pn0, pn1 = 10**(n-1), 10**n\n",
    "        for overlap in [0, 1]:\n",
    "            for x in range(pn1-1, pn0-1, -1):\n",
    "                s = str(x)\n",
    "                y = int(s + s[::-1][overlap:])\n",
    "                for a in range(pn1-1, pn0-1, -1):\n",
    "                    if a * a < y:\n",
    "                        break\n",
    "                    if y % a != 0 or y // a < pn0:\n",
    "                        continue\n",
    "                    return y % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1: \n",
    "            return 9\n",
    "        \n",
    "        const = 1\n",
    "        while const < 10**n:\n",
    "            upper = 10**n - const\n",
    "            lower = int(str(upper)[::-1])\n",
    "            if const**2-lower*4 >= 0 and (const**2-lower*4)**0.5 == int((const**2-lower*4)**0.5):\n",
    "                return (upper*10**n + lower) % 1337\n",
    "            const += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10**n-1\n",
    "        for i in range(upper,upper//10,-1):\n",
    "            x = str(i)\n",
    "            for j in range(len(str(i))-1,-1,-1):\n",
    "                x += str(i)[j]\n",
    "            x = int(x)\n",
    "            print(x)\n",
    "            z = upper\n",
    "            while z*z>=x:\n",
    "                if x % z == 0:\n",
    "                    return x % 1337\n",
    "                z-=1\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):  # 枚举回文数的左半部分\n",
    "            p, x = left, left\n",
    "            while x:\n",
    "                p = p * 10 + x % 10  # 翻转左半部分到其自身末尾，构造回文数 p\n",
    "                x //= 10\n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:  # x 是 p 的因子\n",
    "                    return p % 1337\n",
    "                x -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "        upper = 10 ** n - 1\n",
    "        for left in range(upper, upper // 10, -1):  # 枚举回文数的左半部分\n",
    "            p, x = left, left\n",
    "            while x:\n",
    "                p = p * 10 + x % 10  # 翻转左半部分到其自身末尾，构造回文数 p\n",
    "                x //= 10\n",
    "            x = upper\n",
    "            while x * x >= p:\n",
    "                if p % x == 0:  # x 是 p 的因子\n",
    "                    return p % 1337\n",
    "                x -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "        if n==2:\n",
    "            return 987\n",
    "        def check(n,target):\n",
    "            for i in range(target//(10**n),int(target**0.5)+1):\n",
    "                if target%i==0 and len(str(target//i))==n:\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(10**n-1,10**(n-1)-1,-1):\n",
    "            target=i*(10**n)+int(str(i)[::-1])\n",
    "            if check(n,target):\n",
    "                return target%1337\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def emumeratePalindrome(\n",
    "    minLength: int, maxLength: int, reverse=False\n",
    ") -> Generator[str, None, None]:\n",
    "    \"\"\"\n",
    "    遍历长度在 `[minLength, maxLength]` 之间的回文数字字符串.\n",
    "    maxLength <= 12.\n",
    "    \"\"\"\n",
    "    if minLength > maxLength:\n",
    "        return\n",
    "    if reverse:\n",
    "        for length in reversed(range(minLength, maxLength + 1)):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in reversed(range(start, end + 1)):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "    else:\n",
    "        for length in range(minLength, maxLength + 1):\n",
    "            start = 10 ** ((length - 1) >> 1)\n",
    "            end = start * 10 - 1\n",
    "            for half in range(start, end + 1):\n",
    "                if length & 1:\n",
    "                    yield f\"{half}{str(half)[:-1][::-1]}\"\n",
    "                else:\n",
    "                    yield f\"{half}{str(half)[::-1]}\"\n",
    "\n",
    "\n",
    "MOD = 1337\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        iter = emumeratePalindrome(1, 2 * n, reverse=True)\n",
    "        lower, upper = 10 ** (n - 1), 10**n - 1\n",
    "        for p in iter:\n",
    "            # 这里用大的范围，是因为从后往前找，[lower,sqrt]里的数多 [sqrt,upper]里的数少\n",
    "            num = int(p)\n",
    "            for factor in range(upper, int(num**0.5), -1):\n",
    "                if num % factor == 0 and upper >= num // factor >= lower:\n",
    "                    return num % MOD\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "        hi = 10 ** n - 1\n",
    "        lo = 10 ** (n - 1)\n",
    "        ma = hi ** 2\n",
    "        half_ma = ma // (10 ** n)\n",
    "        while half_ma >= lo:\n",
    "            pal = int(str(half_ma) + str(half_ma)[::-1])\n",
    "            max_fac = hi // 11 * 11\n",
    "            for fac1 in range(max_fac, lo - 1, -11):\n",
    "                if pal // fac1 > hi:\n",
    "                    break\n",
    "                if pal % fac1 == 0:\n",
    "                    return pal % 1337\n",
    "            half_ma -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1: \n",
    "            return 9\n",
    "        if n == 2:\n",
    "            return 987\n",
    "        \n",
    "        max_num = pow(10,n) - 1\n",
    "        for num in range(max_num,-1,-1):\n",
    "            palinddrome = num\n",
    "            var = num\n",
    "            while var:\n",
    "                palinddrome = palinddrome * 10 + (var % 10)\n",
    "                var //= 10\n",
    "            number = max_num\n",
    "            while number * number >= palinddrome:\n",
    "                if palinddrome % number == 0:\n",
    "                    return palinddrome % 1337\n",
    "                number -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 9\n",
    "\n",
    "        tmpval = int('9'*n)\n",
    "        #s = tmpval*tmpval\n",
    "\n",
    "        def getnumber(left,lenthodd):\n",
    "            ans = left\n",
    "            if lenthodd:\n",
    "                left //= 10\n",
    "            while left>0:\n",
    "                ans = ans*10+(left%10)\n",
    "                left //= 10\n",
    "            return ans\n",
    "        l = 10**(n-1)\n",
    "        r = 10**n\n",
    "\n",
    "        def check(number):\n",
    "            x = max(10**(n-1),number//r)\n",
    "            while x*x<=number:\n",
    "                if number%x==0 and l<=number//x<r:\n",
    "                    return True\n",
    "                x += 1\n",
    "            return False\n",
    "        lenthodd = False\n",
    "        ans = 0 \n",
    "        for left in range(tmpval,l,-1):\n",
    "            number = getnumber(left,False)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                return ans%1337\n",
    "\n",
    "        for left in range(tmpval,tmpval//10,-1):\n",
    "            number = getnumber(left,True)\n",
    "            if check(number):\n",
    "                ans = max(ans,number)\n",
    "                break\n",
    "        return ans%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPalindrome(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 9\n",
    "\n",
    "        const = 1\n",
    "        while const < 10 ** n:\n",
    "            upper = 10 ** n - const\n",
    "            lower = int(str(upper)[::-1])\n",
    "            if const ** 2 - lower * 4 >= 0 and (const ** 2 - lower * 4) ** 0.5 == int((const ** 2 - lower * 4) ** 0.5):\n",
    "                return (upper * 10 ** n + lower) % 1337\n",
    "            const += 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
